/*
 * SplitVec.h
 *
 *  Created on: 2012-9-5
 *      Author: yangentao@gmail.com
 */

#pragma once;
#include "baseutil.h"
#include <boost/scoped_array.hpp>

namespace yet{
#define SPLIT_VEC_MIN_CAP	8

template<typename T>
class SplitVec {
protected:
	boost::scoped_array<T> sarray;
	int capcity;

	int gapPos;
	int gapLen;

public:
	SplitVec() :
			capcity(0), gapPos(0), gapLen(0) {
		ensureCapcity(SPLIT_VEC_MIN_CAP);
	}
	SplitVec(int capcity_) :
			capcity(0), gapPos(0), gapLen(0) {
		ensureCapcity(Max(SPLIT_VEC_MIN_CAP, capcity_));
	}
	SplitVec(const SplitVec<T>& other) :
			capcity(0), gapPos(0), gapLen(0) {
		copyFrom(other);
	}
	virtual ~SplitVec() {
	}
protected:
	int allocSize(int increase) const {
		assert(increase>=0);
		int smallest = length() + increase;
		if (smallest > 512) {
			return smallest + 512;
		} else {
			return smallest * 2;
		}
	}

	void gapTo(int index, int increase = 0) {
		assert(index >=0);
		assert(increase >=0);
		assert(index <= length());
		int delta = index - gapPos;
		if (sarray && gapLen >= increase) {
			if (delta == 0) {
				; //nothing
			} else if (delta > 0) {
				ArrayMove(part1Buffer() + part1Len(), part2Buffer(), delta);
			} else { //delta <0
				ArrayMove(part2Buffer() + delta, part1Buffer() + part1Len() + delta, -delta);
			}
		} else {
			int newCap = allocSize(increase);
			T* buf = new T[newCap];
			if (sarray) {
				if (delta == 0) {
					ArrayMove(buf, part1Buffer(), part1Len());
					ArrayMove(buf + newCap - part2Len(), part2Buffer(), part2Len());
				} else if (delta > 0) {
					ArrayMove(buf, part1Buffer(), part1Len());
					ArrayMove(buf + part1Len(), part2Buffer(), delta);
					ArrayMove(buf + newCap - (part2Len() - delta), part2Buffer() + delta, part2Len() - delta);
				} else { //delta < 0
					ArrayMove(buf, part1Buffer(), part1Len() + delta);
					ArrayMove(buf + newCap - part2Len() + delta, part1Buffer() + part1Len() + delta, -delta);
					ArrayMove(buf + newCap - part2Len(), part2Buffer(), part2Len());
				}
			}
			gapLen += newCap - capcity;
			capcity = newCap;
			sarray.reset(buf);
		}
		gapPos = index;
	}
	inline int innerIndex(int index) const {
		return index >= gapPos ? index + gapLen : index;
	}
	inline int part1Len() const {
		return gapPos;
	}
	inline int part2Len() const {
		return capcity - gapPos - gapLen;
	}
	inline int part1Index() const {
		return 0;
	}
	inline int part2Index() const {
		return gapPos + gapLen;
	}
	inline T* part1Buffer() const {
		return sarray.get();
	}
	inline T* part2Buffer() const {
		return sarray.get() + part2Index();
	}
public:
	SplitVec<T> operator=(const SplitVec<T>& other) {
		copyFrom(other);
		return *this;
	}
	void copyFrom(const SplitVec<T>& other) {
		if (capcity < other.length()) {
			capcity = other.length();
			gapPos = capcity;
			gapLen = 0;
			sarray.reset(new T[capcity]);
			ArrayMove(sarray.get(), 0, other.sarray.get(), other.part1Index(), other.part1Len());
			ArrayMove(sarray.get(), other.part1Len(), other.sarray.get(), other.part2Index(), other.part2Len());
		} else {
			ArrayMove(sarray.get(), 0, other.sarray.get(), other.part1Index(), other.part1Len());
			ArrayMove(sarray.get(), other.part1Len(), other.sarray.get(), other.part2Index(), other.part2Len());
			gapPos = other.length();
			gapLen = capcity - other.length();
		}
	}

	inline T* getBuffer() {
		gapTo(length());
		return sarray.get();
	}
	void ensureCapcity(int capcity_) {
		assert(capcity_>=0);
		if (capcity < capcity_) {
			capcity_ = max(capcity_, 8);
			T* buf = new T[capcity_];
			if (sarray) {
				ArrayMove(buf, 0, sarray.get(), part1Index(), part1Len());
				ArrayMove(buf, part1Len(), sarray.get(), part2Index(), part2Len());
			}
			int len = length();
			gapPos = len;
			gapLen = capcity_ - len;
			capcity = capcity_;
			sarray.reset(buf);
		}
	}
	inline int getCapcity() {
		return capcity;
	}
	inline int length() const {
		return capcity - gapLen;
	}
	inline bool empty() const {
		return length() == 0;
	}
	inline T get(int index) const {
		assert(index>=0);
		assert(index < length());
		return sarray[innerIndex(index)];

	}
	T& getRef(int index) const {
		assert(index < length());
		return sarray[innerIndex(index)];

	}
	inline T operator[](int index) const {
		assert(index >=0 && index < length());
		return get(index);
	}
	T& operator[](int index) {
		assert(index >=0 && index < length());
		return getRef(index);
	}
	inline void set(int index, const T& value) {
		assert(index < length());
		sarray[innerIndex(index)] = value;
	}
	inline T first() const {
		assert(length() > 0);
		return get(0);
	}
	inline T last() const {
		assert(length() > 0);
		return get(length() - 1);
	}
	inline void append(const T& val) {
		replace(length(), 0, &val, 1);
	}
	inline void append(const T* values, int count) {
		replace(length(), 0, values, count);
	}
	inline void insert(int index, const T& val) {
		replace(index, 0, &val, 1);
	}
	inline void insert(int index, const T* values, int count) {
		replace(index, 0, values, count);
	}
	inline void remove(int index) {
		replace(index, 1, 0, 0);
	}
	inline void remove(int index, int len) {
		replace(index, len, 0, 0);
	}

	void replace(int from, int len, const T* arr, int arrLen) {
		assert(from>=0);
		assert(len>=0);
		assert(arrLen>=0);
		if (!len && !arrLen) {
			return;
		}
		assert(from + len <= length());
		int lenDelta = arrLen - len;
		gapTo(from, max(0, lenDelta));
		ArrayMove(sarray.get(), from, arr, 0, arrLen);
		gapPos = from + arrLen;
		gapLen -= lenDelta;
	}
	inline void getRange(T* buf, int from, int len) const {
		if (len) {
			assert(from>=0);
			assert(len>=0);
			assert(from + len <= length());
			for (int i = 0; i < len; ++i) {
				buf[i] = get(i + from);
			}
		}
	}

	bool equals(const SplitVec& other) {
		int len = other.length();
		if (length() == len) {
			if (len) {
				for (int i = 0; i < len; ++i) {
					if (get(i) != other[i]) {
						return false;
					}
				}
				return true;
			} else {
				return true;
			}
		}
		return false;
	}
	bool equals(const T* other, int len) {
		assert(len >=0);
		if (length() == len) {
			if (len) {
				if (other) {
					for (int i = 0; i < len; ++i) {
						if (get(i) != other[i]) {
							return false;
						}
					}
					return true;
				} else {
					return false;
				}
			} else {
				return true;
			}
		}
		return false;
	}

public:
	void dump(const char* prefix = 0) {
		if (prefix) {
			cout << prefix;
		}
		cout << "Capcity: " << capcity << "\tGapPos: " << gapPos << "\tGapLen:" << gapLen << endl;
		cout << "[";
		for (int i = 0; i < capcity; ++i) {
			if (i >= gapPos && i < gapPos + gapLen) {
				if (i == gapPos) {
					cout << "[* ";
				} else if (i == gapPos + gapLen - 1) {
					cout << "*] ";
				} else {
					cout << "* ";
				}
			} else {
				cout << get(i >= gapPos ? i - gapLen : i) << " ";
			}
		}
		cout << "]";
		cout << endl;
	}
};

}
